package problem1314;

//1314.矩阵区域和
//https://leetcode.cn/problems/matrix-block-sum/

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat.length, m = mat[0].length;
        int[][] sum = new int[n+1][m+1];
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i-1][j-1];
            }
        }

        int[][] ret = new int[n][m];
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                int x1 = i-k > 0 ? i-k : 1;
                int y1 = j-k > 0 ? j-k : 1;
                int x2 = i+k <= n ? i+k : n;
                int y2 = j+k <= m ? j+k : m;
                ret[i-1][j-1] = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
            }
        }
        return ret;
    }
}